42. Trapping Rain Water

Hard

424078FavoriteShare

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

1. 横向计算

class Solution:
    def trap(self, nums: List[int]) -> int:
        if not nums: return 0
        res = 0
        for c in range(max(nums), 0, -1):
            idx = [i for i,x in enumerate(nums) if x >= c ]
            if len(idx) > 1:
                res += (idx[-1] - idx[0] - len(idx) + 1)
        
        return res

时间复杂度 O(m*n)长✖️高

2. 纵向计算

求每一列的水，我们只需要关注当前列高度，以及左边最高的墙，右边最高的墙就够了，在根据木桶效应，从左右最高墙里选择一个最矮的墙，和当前列计算高度差就行了。

class Solution:
    def trap(self, nums: List[int]) -> int:
        if not nums: return 0
        res = 0
        for i in range(1,len(nums)-1):
            l = max(nums[:i])
            r = max(nums[i+1:])
            dif = min(l, r)
            if dif > nums[i]:
                res += dif-nums[i]
        
        return res

时间复杂度：O（n²），遍历每一列需要 n，找出左边最高和右边最高的墙加起来刚好又是一个 n，所以是 n²。

空间复杂度：O（1）。

由此发现时间复杂度极高，有没有合适的方法解决呢？那就需要用到下面的DP改良方法了。

3. DP改良版

   同样是去寻找左边最高的墙，右边最高的墙，我们不用每到达新的一列，就重复的向前向后遍历，而是先遍历用DP array存储好，计算时候拿来直接用就行了。

class Solution:
    def trap(self, nums: List[int]) -> int:
        if not nums: return 0
        L = [0]*len(nums)
        R = [0]*len(nums)
        res = 0
        for i in range(1, len(nums)):
            L[i] = max(L[i-1], nums[i-1])
        for i in range(len(nums)-2, -1, -1):
            R[i] = max(R[i+1], nums[i+1])
        for i in range(1, len(nums)):
            dif = min(L[i], R[i])
            if dif > nums[i]:
                res += dif - nums[i]
        
        return res

时间复杂度：O（n），只使用了3个for循环，两个分别用来从左到右，从右到左计算目前已知最高的墙。

空间复杂度：O（n）。有得必有失，需要用两个和输入一样大小的list存储dp结果

4. stack

   详细参考https://www.cnblogs.com/grandyang/p/4402392.html，主旨是维护一个单调递减栈。

class Solution:
    def trap(self, nums: List[int]) -> int:
        stack = [] # using monotone stack (decreasing)
        res = 0
        i = 0
        while i < len(nums):
            # if the top element of stack is highter than cur element, add it 
            if not stack or nums[stack[-1]] >= nums[i]: 
                stack.append(i)
                i += 1
            else:
                puddle = nums[stack.pop()]
                if not stack: continue
                res += (min(nums[i], nums[stack[-1]]) - puddle) * (i - stack[-1] - 1)
        return res